package test;

/**
 * @author haomin
 * @date 2022/03/28 18:51
 **/
//插入排序
public class class_test_03_28 {
    public static void insertionSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j >= 0 ; j--) {
                if(arr[j] < arr[i]){
                    swap(arr,j,i);
                }
            }
        }
    }
    private static void swap(int[] arr, int j, int i) {
        int temp = arr[i];
        arr[j] = arr[i];
        arr[i] =temp;
    }

    //反转链表
    //头插法
    public static Node change(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Node dummyNode = new Node(-1);
        while (head != null){
            Node node = new Node(head.value);
            node.next = dummyNode.next;
            dummyNode.next = node;
            head = head.next;
        }
        return dummyNode.next;
    }

    //二叉树高度
    public static int high(TreeNode1 root){
        if(root == null){
            return 0;
        }
        return 1 + Math.max(high(root.left),high(root.right));
    }
}

class TreeNode1{
    int value;
    TreeNode1 left;
    TreeNode1 right;

    public TreeNode1(int value, TreeNode1 left, TreeNode1 right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

class Node{
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}



